package com.ly.algorithm.DataStructures.problem;

/**
 * @Classname SelectNumber
 * @Description 在一堆数字中选出不相邻的数，相加的最大值
 * @Date 2020/5/4 10:55
 * @Author 冷心影翼
 */
public class SelectNumber {

    public static void main(String[] args) {
        int[] arr = {1,2,4,1,7,8};
        System.out.println(selectNumber(arr,5));
        System.out.println(selectNumber2(arr));
    }

    public static int selectNumber(int[] arr,int n) {
        if(n<=1) {
            if(n==0) {
                return arr[0];
            }
            return Math.max(arr[0],arr[1]);
        }else {
            return Math.max(selectNumber(arr,n-2)+arr[n],selectNumber(arr,n-1));
        }
    }

    public static int selectNumber2(int[] arr) {
        int[] optArr = new int[arr.length];
        optArr[0] = arr[0];
        optArr[1] = arr[1];
        for (int i = 2; i < arr.length; i++) {
            optArr[i] = Math.max(optArr[i-2] + arr[i],optArr[i-1]);
        }
        return optArr[arr.length-1];
    }
}

/**
* @Author: 冷心影翼
* @Description: 在一堆数字中能选出数字相加 = 给定数字
* @Date: 2020/5/4  11:30
**/
class SubNumber{

    public static void main(String[] args) {
        int[] arr = {3,34,4,12,5,2};
//        System.out.println(subNumber(arr,5,11));
        System.out.println(subNumber2(arr, 1));
//        subNumber3(7,3);
    }

    public static boolean subNumber(int[] arr,int n,int num) {
        if(n==0) {
            if(arr[0] == num) {
                return true;
            }else {
                return false;
            }
        }else {
            if(arr[n]>num) {
                return subNumber(arr,n-1,num);
            }else if(arr[n]==num) {
                return true;
            }else {
                return subNumber(arr,n-1,num-arr[n]) || subNumber(arr,n-1,num);
            }
        }
    }

    public static boolean subNumber2(int[] arr,int num) {
        boolean[] optArr = new boolean[arr.length];
        optArr[0] = arr[0]==num?true:false;
        for(int i=1;i<arr.length;i++) {
            optArr[i] = optArr[0];
        }
        return true;
    }

    public static void subNumber3(int m,int n){

        if(n == 1) {
            System.out.println(m);
            return ;
        }
        for(int i=1;i<=m;i++) {
//            System.out.print(i+" ");
            subNumber3(m-i,n-1);
            m = 7;
        }
    }
}